package com.mjf.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 实现逆波兰(后缀表达式)计算器
 * <p>
 * 实现思路：
 * 从左到右遍历逆波兰表达式
 *   - 如果是数字直接入栈
 *   - 如果是符号，从栈中取出两个数字执行运算后将结果存入栈
 */
public class PolandNotation {
    public static void main(String[] args) {

        // 中缀表达式转列表
        List<String> infixExpressionList = toInfixExpressionList("12.8 + (2 - 3.55)*4+10/5.0");
        System.out.println("中缀表达式List: " + infixExpressionList);
        // 中缀表达式转后缀表达式
        List<String> suffixExpression = parseSuffixExpression(infixExpressionList);
        System.out.println("后缀表达式List: " + suffixExpression);

        // 创建栈存放数字
        Stack<Double> stack = new Stack<>();

        // 切分并遍历逆波兰表达式
        for (String item : suffixExpression) {
            if (item.matches("\\d+\\.*\\d*")) {
                // 如果是数字直接入栈
                stack.push(Double.parseDouble(item));
            } else {
                // 如果是符号，从栈中取出两个数字执行运算后将结果存入栈
                double num1 = stack.pop();
                double num2 = stack.pop();
                stack.push(cal(num2, num1, item));  // 注意数字顺序
            }
        }

        System.out.printf("%s = %f\n", suffixExpression, stack.pop());

    }

    /**
     * 计算方法
     */
    public static double cal(double num1, double num2, String operator) {
        double res = 0;
        switch (operator) {
            case "+":
                res = num1 + num2;
                break;
            case "-":
                res = num1 - num2;
                break;
            case "*":
                res = num1 * num2;
                break;
            case "/":
                res = num1 / num2;
                break;
            default:
                break;
        }
        return res;
    }

    /**
     * 将中缀表达式切分后存放到列表，方便后续遍历
     */
    public static List<String> toInfixExpressionList(String expression) {
        // 去除表达式中空白部分
        String str = expression.replaceAll("\\s+", "");
        List<String> res = new ArrayList<>();
        // 操作符
        List<Character> operators = Arrays.asList('+', '-', '*', '/', '(', ')');
        // 拼接数字
        StringBuilder number = new StringBuilder();

        for (int i = 0; i < str.length(); i++) {
            char point = str.charAt(i);
            if (operators.contains(point)) {
                // 遍历到运算符
                if (number.length() != 0) {
                    res.add(number.toString());
                }
                res.add("" + point);
                number = new StringBuilder();   // 清空数字
            } else {
                number.append(point);
            }
        }

        // 最后一个字符不是操作符时，将最后一个数字放到列表
        if (number.length() != 0) {
            res.add(number.toString());
        }

        return res;
    }

    /**
     * 返回运算符优先级
     *
     * @return 优先级
     */
    public static int priority(String operator) {
        if ("*".equals(operator) || "/".equals(operator)) {
            return 1;
        } else if ("+".equals(operator) || "-".equals(operator)) {
            return 0;
        } else {
            return -1;  // 假定表达式只有 + - * /
        }
    }

    /**
     * 中缀表达式转后缀表达式
     * <p>
     * 备注：
     * 1. 实现流程见README.md
     * 2. 因为s2栈在整个过程中都没有pop操作，最后还需要逆序输出比较麻烦。这里直接使用ArrayList代替
     *
     * @param infixExpression 中缀表达式
     * @return 后缀表达式
     */
    public static List<String> parseSuffixExpression(List<String> infixExpression) {
        Stack<String> s1 = new Stack<String>(); // 存储运算符
        ArrayList<String> s2 = new ArrayList<>();   // 存储中间结果及最后结果
        List<String> operators = Arrays.asList("+", "-", "*", "/", "(", ")");

        for (String item : infixExpression) {
            if (operators.contains(item)) {
                // 运算符
                if (s1.isEmpty() || "(".equals(item) || "(".equals(s1.peek()) || priority(item) > priority(s1.peek())) {
                    s1.push(item);
                } else if (")".equals(item)) {
                    while (!"(".equals(s1.peek())) {
                        s2.add(s1.pop());
                    }
                    s1.pop();   // 删除当前右括号对应左括号
                } else {
                    while (!s1.isEmpty() && !"(".equals(s1.peek()) && priority(item) <= priority(s1.peek())) {
                        s2.add(s1.pop());
                    }
                    s1.push(item);
                }
            } else {
                s2.add(item);
            }
        }

        while (!s1.isEmpty()) {
            s2.add(s1.pop());
        }

        return s2;
    }
}
